package com.zhf;

/**
 * 给定一个链表，判断链表中是否有环。存在环返回 true ，否则返回 false，约束时间复杂度为 O(n)。
 */
public class Test2 {

    public static boolean isRing(Node head){
        if(head == null) return false;
        Node slow = head;       // 慢指针
        Node fast = head.next;  // 快指针
        while(fast != null && slow != null){

            // 快指针和慢指针重合，说明该链表有环
            if(slow == fast) return true;
            slow = slow.next;           //慢指针步长为1
            fast = fast.next.next;      // 快指针步长为2
        }
        return false;
    }


    public static void main(String[] args) {
        Node n1=new Node(1);
        Node n2=new Node(2);
        Node n3=new Node(3);
        Node n4=new Node(4);
        Node n5=new Node(5);
        n1.next=n2;
        n2.next=n3;
        n3.next=n4;
        n4.next=n5;
//        n5.next=n1;
        System.out.println(isRing(n1));

    }



}

class Node{
    int data;
    Node next;

    public Node(int data){
        this.data = data;
    }
}
